BZOJ1901 Dynamic Rankings <整体二分>

Problem

Dynamic Rankings

Description

给定一个含有个数的序列。
对于给定的，请回答在中第小的数是多少。
在询问中会有操作改变一些的值，改变后，需要针对改变后的继续回答上面的问题。

Input

第一行有两个正整数。
分别表示序列的长度和指令的个数。
第二行有个数，表示，这些数都小于。
接下来的行描述每条指令，每行的格式是下面两种格式中的一种。

表示询问指令，询问中第小的数。
表示把改变成为。

Output

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input

Sample Output

1
2

3
6

HINT

标签：整体二分

Solution

整体二分经典题，直接上整体二分即可。

考虑将所有询问离线下来，对所有询问同时进行二分答案，二分函数有四个参数，表示答案在区间内的询问为在询问序列上位置在之间的所有询问。
如果，则可知询问序列上位置在间的所有询问答案均为。否则，我们需要把间的所有询问分为前后两部分，前一部分为答案在间的所有询问，后一部分为答案在间的所有询问。这个过程用一棵树状数组判断一下间每个询问的答案在哪边即可。
然而我们还需要维护修改操作。对于修改操作，我们同样将其加入整体二分。当询问函数将答案限制到时，只有参数在间的修改操作才会对这个间的询问答案产生影响。于是将每个修改拆成两个操作，即在某位置上删除一个数和加入一个数。
用树状数组维护时，若删除或加入的数在间，在树状数组上对应位置或。对于询问，若询问区间为，那么该询问的值为树状数组上位置上的值之和。这样一来，统计的是每个询问区间内小于等于的数的个数，若，则答案一定在间；否则，答案一定大于。分治处理即可。

由于整体二分会带来一个，枚举每个询问并用树状数组判断其答案在左边还是右边需要，故总复杂度为。

Code

#include <bits/stdc++.h>
#define MAX_N 20000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int N, M, Q, cnt, val[MAX_N+5], ans[MAX_N+5];
struct node {int id, tp, a, b, k, s;} p[MAX_N+5], q[MAX_N+5];
int num[MAX_N+5], tr[MAX_N+5]; bool mrk[MAX_N+5];
void inc(int p) {for (; p <= N; p += (p&-p)) tr[p]++;}
void dec(int p) {for (; p <= N; p += (p&-p)) tr[p]--;}
int sum(int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[p]; return ret;}
void bi_solve(int l, int r, int s, int t) {
    if (l > r) return;
    if (s == t) {
        for (int i = l; i <= r; i++)
            if (p[i].tp == 3) ans[p[i].id] = s;
        return;
    }
    for (int i = l; i <= r; i++)
        if (p[i].tp == 1 && p[i].b <= mid) inc(p[i].a);
        else if (p[i].tp == 2 && p[i].b <= mid) dec(p[i].a);
        else if (p[i].tp == 3) num[i] = sum(p[i].b)-sum(p[i].a-1);
    for (int i = l; i <= r; i++)
        if (p[i].tp == 1 && p[i].b <= mid) dec(p[i].a);
        else if (p[i].tp == 2 && p[i].b <= mid) inc(p[i].a);
    int lsz = 0;
    for (int i = l; i <= r; i++)
        if (p[i].tp == 3) {
            if (p[i].k <= p[i].s+num[i]) lsz++, mrk[i] = false;
            else p[i].s += num[i], mrk[i] = true;
        } else lsz += (p[i].b <= mid), mrk[i] = (p[i].b > mid);
    for (int i = l, p1 = l, p2 = l+lsz; i <= r; i++)
        if (!mrk[i]) q[p1++] = p[i]; else q[p2++] = p[i];
    for (int i = l; i <= r; i++) p[i] = q[i];
    bi_solve(l, l+lsz-1, s, mid), bi_solve(l+lsz, r, mid+1, t);
}
int main() {
    read(N), read(M);
    for (int i = 1; i <= N; i++)
        read(val[i]), p[++cnt] = (node){0, 1, i, val[i], 0, 0};
    for (int i = 1, a, b, k; i <= M; i++) {
        char opt[2]; scanf("%s", opt);
        if (opt[0] == 'C')
            read(a), read(b), 
            p[++cnt] = (node){0, 2, a, val[a], 0, 0}, 
            p[++cnt] = (node){0, 1, a, (val[a] = b), 0, 0};
        else
            read(a), read(b), read(k), 
            p[++cnt] = (node){++Q, 3, a, b, k, 0};
    }
    bi_solve(1, cnt, 0, INF);
    for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
    return 0;
}